#include <iostream>
#include <string>
using namespace std;

int ans = -1;

bool isprime(int n)
{
    if (n == 1) return false;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

void dfs(string str, int step)
{
    if (step >= str.size())
    {
        int num = stoi(str);
        if (isprime(num))
        {
            if (ans == -1 || ans > num)
                ans = num;
        }
        return;
    }

    if (str[step] == '*')
    {
        int start = (step == 0 ? 1 : 0);
        for (int i = start; i <= 9; i++)
        {
            str[step] = '0' + i;
            dfs(str, step + 1);
            str[step] = '*';
        }
    }
    else
        dfs(str, step + 1);
}

int main()
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        string str;
        cin >> str;
        dfs(str, 0);
        cout << ans << endl;
        ans = -1;
    }

    return 0;
}
